import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeSet;

public abstract class Strategy {
	
	public static final int FOOD_TASK_TIMEOUT = 500;
	public static final int EXPLORE_TASK_TIMEOUT = 200;
	public static final int ATTACK_TASK_TIMEOUT = 200;
	public static final int DETERMINE_ATTACK_DISTANCE = 10;

	protected MyBot mBot;

	// Prioritize which area need to explore and mark them at each turn.
	protected boolean[][] visibleBefore;
	// protected int[][] diffutionExploration;
	protected int[][] explorationPriority;
	protected int[][] previousEnemyMap;
	protected int[][] enemyMap;

	// Attack hill strategy
	protected Set<Tile> enemyHills = new HashSet<Tile>();
	protected int[][] enemyHillsGoalValue;
	protected HashMap<Tile, GoalAgent> enemyHillsGoal = new HashMap<Tile, GoalAgent>();

	// A * path finding
	// To keep track if a particular cell is visited in this search.
	protected boolean[][] visitedSearch;

	protected Tile[][] tiles;
	protected Node[][] nodes;

	protected HashMap<String, Route> routeDictionary = new HashMap<String, Route>();
	protected HashMap<String, Route> routeDictionaryUncomplete = new HashMap<String, Route>();

	protected TreeSet<Tile> mFreeAnts = new TreeSet<Tile>();
	protected ArrayList<Task> foodTask = new ArrayList<Task>();
	protected HashMap<Tile, Task> exploreTask = new HashMap<Tile, Task>();
	protected HashMap<Tile, Task> attackHillTask = new HashMap<Tile, Task>();

	protected HashMap<Tile, IgnoreItem> ignoreList = new HashMap<Tile, IgnoreItem>();

	// TODO: Improve exploration to use diffusion ways.
	// private static final float REDUCTION_RATE = 0.99f;
	// private static final int INVISIBLE_TILE = 2 << 20;
	// private static final int[] INVISIBL_COEFF = {
	// (int) (INVISIBLE_TILE * Math.pow(REDUCTION_RATE, 0)),
	// (int) (INVISIBLE_TILE * Math.pow(REDUCTION_RATE, 1)),
	// (int) (INVISIBLE_TILE * Math.pow(REDUCTION_RATE, 2)),
	// (int) (INVISIBLE_TILE * Math.pow(REDUCTION_RATE, 3)),
	// (int) (INVISIBLE_TILE * Math.pow(REDUCTION_RATE, 4)),
	// (int) (INVISIBLE_TILE * Math.pow(REDUCTION_RATE, 5)),
	// (int) (INVISIBLE_TILE * Math.pow(REDUCTION_RATE, 6)),
	// (int) (INVISIBLE_TILE * Math.pow(REDUCTION_RATE, 7)),
	// (int) (INVISIBLE_TILE * Math.pow(REDUCTION_RATE, 8)),
	// (int) (INVISIBLE_TILE * Math.pow(REDUCTION_RATE, 9)),
	// (int) (INVISIBLE_TILE * Math.pow(REDUCTION_RATE, 10)),
	// };

	int rows;
	int cols;

	public Strategy(MyBot bot) {
		mBot = bot;
		rows = mBot.getAnts().getRows();
		cols = mBot.getAnts().getCols();

		mBot = bot;
		// diffutionExploration = new int[rows][cols];
		explorationPriority = new int[rows][cols];
		previousEnemyMap = new int[rows][cols];
		enemyMap = new int[rows][cols];
		visibleBefore = new boolean[rows][cols];
		tiles = new Tile[rows][cols];
		nodes = new Node[rows][cols];
		visitedSearch = new boolean[rows][cols];
		enemyHillsGoalValue = new int[rows][cols];

		for (int i = 0; i < explorationPriority.length; i++) {
			// Arrays.fill(diffutionExploration[i], 0);
			Arrays.fill(explorationPriority[i], 0);
			Arrays.fill(previousEnemyMap[i], 0);
			Arrays.fill(enemyMap[i], 0);
			Arrays.fill(visibleBefore[i], false);
			Arrays.fill(visitedSearch[i], false);
			Arrays.fill(enemyHillsGoalValue[i], 0);
		}

		for (int i = 0; i < rows; i++) {
			for (int j = 0; j < cols; j++) {
				tiles[i][j] = new Tile(i, j);
				nodes[i][j] = new Node(i, j);
			}
		}

	}

	public abstract void execute();

	protected void updateEnemyHillsLocation(Ants ants) {

		MyBot.debug.log(Debug.DEBUG_ATTACK_DEBUG, "Size: "
				+ ants.getEnemyHills().size());
		MyBot.debug.log(Debug.DEBUG_ATTACK_DEBUG, "Size: " + enemyHills.size());
		MyBot.debug.log(Debug.DEBUG_ATTACK_DEBUG,
				"Size: " + enemyHillsGoal.size());
		// add new hills to set
		for (Tile enemyHill : ants.getEnemyHills()) {
			if (!enemyHills.contains(enemyHill)) {
				enemyHills.add(enemyHill);
				GoalAgent goal = new GoalAgent(mBot.getAnts(), rows, cols);
				goal.setGoal(enemyHill.getRow(), enemyHill.getCol());
				goal.setType(GoalAgent.GoalType.ENEMY_HILL);
				goal.setTiles(tiles);
				enemyHillsGoal.put(enemyHill, goal);
			}
		}

		MyBot.debug.log(Debug.DEBUG_ATTACK_DEBUG, "Size: " + enemyHills.size());
		MyBot.debug.log(Debug.DEBUG_ATTACK_DEBUG,
				"Size: " + enemyHillsGoal.size());
		// Remove hills if the hill is already die when not visible.
		for (Iterator<Tile> enemyHillItr = enemyHills.iterator(); enemyHillItr
				.hasNext();) {
			Tile enemyHill = enemyHillItr.next();
			if (ants.isVisible(enemyHill)
					&& !ants.getEnemyHills().contains(enemyHill)) {
				enemyHillItr.remove();
				enemyHillsGoal.remove(enemyHill);
			}
		}
		MyBot.debug.log(Debug.DEBUG_ATTACK_DEBUG, "Size: " + enemyHills.size());
		MyBot.debug.log(Debug.DEBUG_ATTACK_DEBUG,
				"Size: " + enemyHillsGoal.size());

		Iterator<Entry<Tile, GoalAgent>> itr = enemyHillsGoal.entrySet()
				.iterator();
		while (itr.hasNext()) {
			Entry<Tile, GoalAgent> entry = itr.next();
			entry.getValue().createDiffionMap();
			MyBot.debug.log(Debug.DEBUG_ATTACK_DEBUG, "Create map");
		}
		MyBot.debug.log(Debug.DEBUG_ATTACK_DEBUG, "Size: " + enemyHills.size());
		MyBot.debug.log(Debug.DEBUG_ATTACK_DEBUG,
				"Size: " + enemyHillsGoal.size());

	}

	protected void updateVisibleArea() {
		Ants ants = mBot.getAnts();
		for (int i = 0; i < rows; i++) {
			for (int j = 0; j < cols; j++) {
				visibleBefore[i][j] = visibleBefore[i][j]
						|| ants.isVisible(tiles[i][j]);
			}
		}
	}

	protected void updateExplorationMap() {

		Ants ants = mBot.getAnts();
		Tile tempTile = null;

		for (int i = 0; i < previousEnemyMap.length; i++) {
			System.arraycopy(enemyMap[i], 0, previousEnemyMap[i], 0,
					ants.getCols());
		}

		for (int i = 0; i < enemyMap.length; i++) {
			for (int j = 0; j < enemyMap[i].length; j++) {
				tempTile = tiles[i][j];

				if (ants.getTurnTime() == 1) {
					// First round,
					// 1. visible area is reset.
					// 2. invisible area may contains enemy.
					if (ants.isVisible(tempTile)) {
						enemyMap[i][j] = 0;
					} else {
						enemyMap[i][j]++;
					}
				} else {
					// Other round,
					// 1. visible area
					// a. Enemy Ants - +2
					// b. Adjacent to enemy ants - +1
					// c. Others - reset
					// 2. invisible area
					// a. adjacent to previous possible enemy - +1
					// b. not adjacent to previous possible enemy - reset.
					if (ants.isVisible(tempTile)) {
						if (ants.getIlk(tempTile) == Ilk.ENEMY_ANT) {
							enemyMap[i][j] += 2;
						} else if (isAdjacentToEnemy(tempTile)) {
							enemyMap[i][j] += 1;
						} else {
							enemyMap[i][j] = 0;
						}
					} else {
						enemyMap[i][j] = (isAdjacentToPossibleEnemy(tempTile,
								previousEnemyMap)) ? enemyMap[i][j] + 1 : 0;
					}
				}
			}
		}

		for (int i = 0; i < explorationPriority.length; i++) {
			for (int j = 0; j < explorationPriority[i].length; j++) {
				tempTile = tiles[i][j];

				if (!ants.isVisible(tempTile)) {
					explorationPriority[i][j]++;
				} else {
					// Reset the exploration priority when the area is visible.
					explorationPriority[i][j] = 0;
				}
			}
		}

		// // Create exploration maps(Diffusion).
		// for (int i = 0; i < diffutionExploration.length; i++) {
		// Arrays.fill(diffutionExploration[i], 0);
		// }

		// StringBuilder strB = new StringBuilder();
		// for (int i = 0; i < explorationPriority.length; i++) {
		// strB.append(String.format("%3d ", i));
		// }
		// MyBot.debug.log(Debug.DEBUG_EXPLORE_PRIORITY_DEBUG,
		// String.format(" col : %s", strB));
		//
		// for (int i = 0; i < explorationPriority.length; i++) {
		// String str = "";
		// for (int j = 0; j < explorationPriority[i].length; j++) {
		// str += String.format("%3d ", explorationPriority[i][j]);
		// }
		// MyBot.debug.log(Debug.DEBUG_EXPLORE_PRIORITY_DEBUG,
		// String.format(" %3d : %s", i, str));
		// }
	}

	// Implement diffusion on enemy's hill.
	protected void updateEnemyHillDiff() {

		// Reset all value.
		for (int i = 0; i < this.enemyHillsGoalValue.length; i++) {
			Arrays.fill(this.enemyHillsGoalValue[i], 0);
		}

		Iterator<Entry<Tile, GoalAgent>> itr = this.enemyHillsGoal.entrySet()
				.iterator();
		while (itr.hasNext()) {
			Entry<Tile, GoalAgent> entry = itr.next();
			GoalAgent goalAgent = entry.getValue();

			for (int i = 0; i < goalAgent.map.length; i++) {
				for (int j = 0; j < goalAgent.map[i].length; j++) {
					this.enemyHillsGoalValue[i][j] += goalAgent.map[i][j];
				}
			}
		}

		// debugEnemyHillsGoal();

	}

	private void debugEnemyHillsGoal() {
		StringBuilder strB = new StringBuilder();
		for (int i = 0; i < enemyHillsGoalValue.length; i++) {
			strB.append(String.format("%7d ", i));
		}
		MyBot.debug.log(Debug.DEBUG_ATTACK_DEBUG,
				String.format(" col : %s", strB));

		for (int i = 0; i < enemyHillsGoalValue.length; i++) {
			String str = "";
			for (int j = 0; j < enemyHillsGoalValue[i].length; j++) {
				str += String.format("%7d ", enemyHillsGoalValue[i][j]);
			}
			MyBot.debug.log(Debug.DEBUG_ATTACK_DEBUG,
					String.format(" %7d : %s", i, str));
		}
	}

	private boolean isAdjacentToEnemy(Tile tile) {

		Ants ants = mBot.getAnts();
		for (Aim direction : Aim.values()) {
			if (ants.getIlk(tile, direction) == Ilk.ENEMY_ANT) {
				return true;
			}
		}
		return false;
	}

	private boolean isAdjacentToPossibleEnemy(Tile tile,
			int[][] previousEnemyMap) {

		Ants ants = mBot.getAnts();
		Tile tempTile;
		for (Aim direction : Aim.values()) {
			tempTile = ants.getTile(tile, direction);
			if (previousEnemyMap[tempTile.getRow()][tempTile.getCol()] > 0) {
				return true;
			}
		}
		return false;
	}

	public Tile getNearestExplorationArea(Tile tile, boolean acceptSame) {
		boolean same = true;
		Ants ants = mBot.getAnts();

		Node current = null;
		Node node = null;
		int visibleRadius = (int) Math.sqrt(ants.getViewRadius2());
		int dr = 0;
		int dc = 0;
		int visibleR = 0;
		int visibleC = 0;
		int row = 0;
		int col = 0;
		int stopCellR = 0;
		int stopCellC = 0;
		int cooefficient = 0;
		int highestCooef = 0;

		for (MyAim direction : MyAim.values()) {
			switch (direction) {
			case EAST:
				visibleR = 0;
				visibleC = visibleRadius;
				break;
			case WEST:
				visibleR = 0;
				visibleC = -visibleRadius;
				break;
			case NORTH:
				visibleR = -visibleRadius;
				visibleC = 0;
				break;
			case SOUTH:
				visibleR = visibleRadius;
				visibleC = 0;
				break;
			case NORTH_EAST:
				visibleR = -visibleRadius / 2;
				visibleC = visibleRadius / 2;
				break;
			case NORTH_WEST:
				visibleR = -visibleRadius / 2;
				visibleC = -visibleRadius / 2;
				break;
			case SOUTH_EAST:
				visibleR = visibleRadius / 2;
				visibleC = visibleRadius / 2;
				break;
			case SOUTH_WEST:
				visibleR = visibleRadius / 2;
				visibleC = -visibleRadius / 2;
				break;
			}

			dr = direction.getRowDelta();
			dc = direction.getColDelta();

			cooefficient = 1;
			stopCellR = (tile.getRow() + visibleR + dr + this.rows) % this.rows;
			stopCellC = (tile.getCol() + visibleC + dc + this.cols) % this.cols;
			Node stopNode = nodes[stopCellR][stopCellC];

			MyBot.debug.log(Debug.DEBUG_EXPLORE_PRIORITY,
					String.format("Stop Node: %s", stopNode));
			int i = 0;
			boolean reachStopNode = false;
			do {
				row = (tile.getRow() + (dr * i) + this.rows) % this.rows;
				col = (tile.getCol() + (dc * i) + this.cols) % this.cols;
				node = nodes[row][col];
				if (ants.getIlk(node).isPassable()) {
					cooefficient = cooefficient + 3;
				} else {
					cooefficient = cooefficient + 1;
				}
				i++;

				if (node.equals(stopNode)) {
					reachStopNode = true;
				}

				MyBot.debug
						.log(Debug.DEBUG_EXPLORE_PRIORITY, String.format(
								"Node: %s, %s (%d)", reachStopNode, node,
								cooefficient));
			} while (!reachStopNode || !ants.getIlk(node).isPassable());
			cooefficient = cooefficient
					* explorationPriority[node.getRow()][node.getCol()];

			if (current == null) {
				highestCooef = cooefficient;
				current = node;
			} else {
				if (highestCooef != cooefficient) {
					same = false;
				}

				if (highestCooef <= cooefficient) {
					highestCooef = cooefficient;
					current = node;
				}
			}

			// MyBot.debug.log(Debug.DEBUG_EXPLORE,
			// String.format("%s: current: %s", tile, current));
		}

		return ((!acceptSame && same) ? null : current);
	}

	public Tile getAttackHill(Tile current) {

		boolean same = true;
		int highestCooef = 0;
		Tile highest = null;

		if (!this.enemyHills.isEmpty()) {
			for (Aim direction : Aim.values()) {
				final Tile tile = getTile(current, direction);

				if (highest == null) {
					highestCooef = this.enemyHillsGoalValue[tile.getRow()][tile
							.getCol()];
					highest = tile;
				} else {
					if (highestCooef < this.enemyHillsGoalValue[tile.getRow()][tile
							.getCol()]) {
						highestCooef = this.enemyHillsGoalValue[tile.getRow()][tile
								.getCol()];
						highest = tile;
						same = false;
					} else if (highestCooef > this.enemyHillsGoalValue[tile
							.getRow()][tile.getCol()]) {
						same = false;
					}
				}
			}
		}

		return highest;// (!same) ? highest : null;
	}

	// public Tile getNearestExplorationArea(Tile tile) {
	//
	// clearNodes();
	//
	// Node start = nodes[tile.getRow()][tile.getCol()];
	// Node current = null;
	// ArrayList<Node> openList = new ArrayList<Node>();
	// openList.add(start);
	//
	// Ants ants = mBot.getAnts();
	//
	// while (!openList.isEmpty()) {
	//
	// Collections.sort(openList);
	// current = openList.remove(0);
	// current.openList = false;
	// // MyBot.debug.log(Debug.DEBUG_EXPLORE, "Current: " + current + "("
	// // + explorationPriority[current.getRow()][current.getCol()]
	// // + ")");
	//
	// if (!visibleBefore[current.getRow()][current.getCol()]
	// || explorationPriority[current.getRow()][current.getCol()] > 10) {
	// // found
	// break;
	// }
	//
	// for (Aim direction : Aim.values()) {
	// Node node = getNode(current, direction);
	// // MyBot.debug.log(Debug.DEBUG_EXPLORE, direction + ": " +
	// // node);
	//
	// if (!node.openList || ! ants.getIlk(node).isPassable()) {
	// // Ignore
	// } else {
	// openList.add(node);
	// }
	//
	// }
	// }
	//
	// for (int i = 0; i < nodes.length; i++) {
	// StringBuilder strB = new StringBuilder();
	// char c;
	// for (int j = 0; j < nodes[i].length; j++) {
	// c = nodes[i][j].openList == false ? 'o' : ' ';
	// if (nodes[i][j] == current) {
	// c = 'X';
	// }
	// strB.append(c);
	// }
	// MyBot.debug.log(Debug.DEBUG_EXPLORE, strB.toString());
	// }
	//
	// return current;
	// }

	public Route getRouteIfExist(Tile start, Tile end) {

		if (start.equals(end)) {
			return null;
		}

		return getRouteInternal(start, end);
	}

	/**
	 * Get a route from tile
	 * 
	 * @param start
	 * @param end
	 * @return
	 */
	public Route getRoute(Tile start, Tile end) {
		return getRoute(start, end, null);
	}

	public Route getRoute(Tile tile1, Tile tile2, RouteCondition condition) {

		long startTime = System.currentTimeMillis();
		if (tile1.equals(tile2)) {
			return null;
		}

		Route route = getRouteInternal(tile1, tile2);

		if (route != null) {
			return route;
		}

		// MyBot.debug.log("RouteDebug", tile1 + ", " + tile2);
		// MyBot.debug.log("RouteDebug", "Clear all nodes");
		// Clear nodes array.
		clearNodes();

		Node start = nodes[tile1.getRow()][tile1.getCol()];
		Node end = nodes[tile2.getRow()][tile2.getCol()];

		Ants ants = mBot.getAnts();

		start.gCost = 0;
		start.fCost = start.gCost + ants.getDistance(start, end);
		ArrayList<Node> openList = new ArrayList<Node>();

		// Add the starting point into open list.
		start.openList = true;
		openList.add(start);

		MyBot.debug.log("RouteDebug", start + "->" + end);
		MyBot.debug.log("RouteDebug", "=================");
		boolean found = false;
		Node currentNode = null;
		while (!openList.isEmpty()) {

			Collections.sort(openList);
			// DEBUG: Print out the current openlist items.
			// for (Iterator<Node> itr = openList.iterator(); itr.hasNext();) {
			// Node n = itr.next();
			// MyBot.debug.log("RouteDebug", n + ": " + n.gCost + ", "
			// + n.fCost);
			// }
			currentNode = openList.remove(0);
			openList.remove(currentNode);
			currentNode.openList = false;

			if (end.equals(currentNode)) {

				// MyBot.debug.log("RouteDebug", "Found.");
				found = true;
				break;
			}

			for (Aim direction : Aim.values()) {

				MyBot.debug.log("RouteDebug", "Current: " + currentNode
						+ ", Direction: " + direction);
				Node node = getNode(currentNode, direction);

				if (!node.openList || !ants.getIlk(node).isPassable()) {
					// Ignore.
					// MyBot.debug.log("RouteDebug", "Ignore.");
				} else {
					if (openList.contains(node)) {
						if (node.gCost < currentNode.gCost + 1) {
							// This path has less effort, update the node to
							// this path.
							node.previous = currentNode;
							node.gCost = currentNode.gCost + 1;
							node.fCost = node.gCost
									+ ants.getDistance(node, end);
							// MyBot.debug.log("RouteDebug", "AfterU: " + node
							// + ", " + node.fCost + ", " + node.gCost);
						} else {
							// nothing to update
							// MyBot.debug.log("RouteDebug",
							// "Nothing to update.");
						}
					} else {
						node.gCost = currentNode.gCost + 1;
						node.fCost = node.gCost
								+ getHeuristicDistance(
										tiles[node.getRow()][node.getCol()],
										end);
						node.previous = currentNode;
						currentNode.next = node;
						// MyBot.debug.log("RouteDebug", "Distance: " +
						// getHeuristicDistance(node, end) + ", "+
						// getHeuristicDistance(tiles[node.getRow()][node.getCol()],
						// end));
						MyBot.debug.log("RouteDebug", node + "->" + end + ": "
								+ node.gCost + "," + node.fCost);
						// MyBot.debug.log("RouteDebug", "OpenList after: "
						// + openList.size());
						openList.add(node);
						// MyBot.debug
						// .log("RouteDebug",
						// "Put: "
						// + node
						// + ", "
						// + openList.get(tiles[node
						// .getRow()][node
						// .getCol()]));
						// MyBot.debug.log("RouteDebug", "AfterN: " + node +
						// ", "
						// + node.fCost + ", " + node.gCost);
						// MyBot.debug.log("RouteDebug", "OpenList after: "
						// + openList.size());
					}
				}
			}
			// MyBot.debug.log("RouteDebug", "OpenList after: " +
			// openList.size());

			// When the condition of the current node could not meet, stop
			// continue looking for the path.
			if (condition != null) {
				condition.updateCurrentNode(currentNode);
				if (!condition.isValid()) {
					break;
				}
			}

			long endTime = System.currentTimeMillis();
			if ((endTime - startTime) > MyBot.ROUTE_TIMEOUT) {
				MyBot.debug.log(Debug.DEBUG_PERFORMANCE, "Break " + end);
				break;
			}
		}

		// Save the route and return the route.
		Route tempRoute = null;
		if (found) {
			currentNode = end;
			boolean explored = true;

			// Check the route found is full visible path.
			// If it is visible path, the path will be saved to completed path.
			// If it is fully visible, the path will be saved and the first
			// unvisible tile will be saved too.
			// The next route will only be perform when the first unvisible tile
			// is become visible again.
			Tile firstUnexploredTile = null;
			MyBot.debug.log("RouteDebug", "Route found.");
			do {
				if (!visibleBefore[currentNode.getRow()][currentNode.getCol()]) {
					MyBot.debug.log("RouteDebug", "Cannot see: " + currentNode);
					explored = false;
					if (firstUnexploredTile == null) {
						firstUnexploredTile = tiles[currentNode.getRow()][currentNode
								.getCol()];
					}
				}
				currentNode.previous.next = currentNode;
				currentNode = currentNode.previous;
			} while (!currentNode.equals(start));

			Node tempNode = start;
			while (tempNode != end) {
				MyBot.debug.log("RouteDebug", tempNode + "->");
				tempNode = tempNode.next;
			}

			if (explored) {
				MyBot.debug.log("RouteDebug", "Save: " + start + "->" + end);
				Node n1 = start;
				Node n2 = end;
				Tile t1;
				Tile t2;
				Aim dir;
				int cost = n2.fCost;
				do {
					dir = ants.getDirections(n1, n1.next).get(0);
					t1 = tiles[n1.getRow()][n1.getCol()];
					t2 = tiles[n2.getRow()][n2.getCol()];
					tempRoute = new Route(t1, t2, Route.RouteType.COMPLETE,
							dir, cost--);
					routeDictionary.put(t1 + "," + t2, tempRoute);
					MyBot.debug.log("RouteDebug", "Save: " + t1 + "->" + t2
							+ ": " + dir);
					n1 = n1.next;
				} while (n1 != n2);
			} else {
				Node n1 = start;
				Node n2 = end;
				Tile t1;
				Tile t2;
				Aim dir;
				int cost = n2.fCost;
				do {
					dir = ants.getDirections(n1, n1.next).get(0);
					t1 = tiles[n1.getRow()][n1.getCol()];
					t2 = tiles[n2.getRow()][n2.getCol()];
					tempRoute = new Route(t1, t2, Route.RouteType.INCOMPLETE,
							dir, cost--, firstUnexploredTile);
					routeDictionaryUncomplete.put(t1 + "," + t2, tempRoute);
					MyBot.debug.log("RouteDebug", "Unexplored Save: " + t1
							+ "->" + t2 + ": " + dir + ", "
							+ firstUnexploredTile);
					n1 = n1.next;
				} while (n1 != n2 && n1 != firstUnexploredTile);
			}
		}

		return getRouteInternal(tile1, tile2);
	}

	/**
	 * Get the route previously saved and returned. Note: The path return maybe
	 * an optimum route, or uncompleted route. For uncompleted route, use
	 * route.getUnexplored() to get the tiles need to explore.
	 * 
	 * @param start
	 * @param end
	 * @return
	 */
	private Route getRouteInternal(Tile start, Tile end) {
		final String routeKey = start.toString() + "," + end.toString();
		if (routeDictionary.containsKey(routeKey)) {
			MyBot.debug.log("RouteDebug", "Optimum route: " + start + "->"
					+ end);
			return routeDictionary.get(routeKey);
		} else if (routeDictionaryUncomplete.containsKey(routeKey)) {
			// Check if the unexplored tiles is still not visible before.
			// If still not visible, then return the old path.
			// If visible before, then return null to treat this as new path.
			Route route = routeDictionaryUncomplete.get(routeKey);
			Tile unexplored = route.getUnexplored();
			MyBot.debug.log("RouteDebug", "UnOptimum route: " + start + "->"
					+ end + ", " + unexplored);
			if (!visibleBefore[unexplored.getRow()][unexplored.getCol()]) {
				MyBot.debug.log("RouteDebug", "UnOptimum route.");
				return routeDictionaryUncomplete.get(routeKey);
			} else {
				routeDictionaryUncomplete.remove(routeKey);
				MyBot.debug.log("RouteDebug", "UnOptimum route: No route.");
			}
		}

		return null;
	}

	protected Tile getTile(Tile tile, Aim direction) {
		int row = (tile.getRow() + direction.getRowDelta()) % rows;
		if (row < 0) {
			row += rows;
		}
		int col = (tile.getCol() + direction.getColDelta()) % cols;
		if (col < 0) {
			col += cols;
		}

		return tiles[row][col];
	}

	private Node getNode(Node node, Aim direction) {
		int row = (node.getRow() + direction.getRowDelta()) % rows;
		if (row < 0) {
			row += rows;
		}
		int col = (node.getCol() + direction.getColDelta()) % cols;
		if (col < 0) {
			col += cols;
		}

		return nodes[row][col];
	}

	protected boolean doMoveDirection(Tile antLoc, Aim direction) {
		Ants ants = mBot.getAnts();
		// Track all moves, prevent collisions
		Tile newLoc = ants.getTile(antLoc, direction);
		if (ants.getIlk(newLoc).isUnoccupied()
				&& !mBot.orders.containsKey(newLoc)) {
			ants.issueOrder(antLoc, direction);
			mBot.orders.put(newLoc, antLoc);
			return true;
		} else {
			return false;
		}
	}

	protected boolean doMoveLocation(Tile antLoc, Tile destLoc) {
		Ants ants = mBot.getAnts();
		// Track targets to prevent 2 ants to the same location
		List<Aim> directions = ants.getDirections(antLoc, destLoc);
		for (Aim direction : directions) {
			if (doMoveDirection(antLoc, direction)) {
				return true;
			}
		}
		return false;
	}

	protected void preventSteppingOwnHill() {

		Ants ants = mBot.getAnts();
		// prevent stepping on own hill
		for (Tile myHill : ants.getMyHills()) {
			mBot.orders.put(myHill, null);
		}
	}

	protected void unblockOwnHill() {
		Ants ants = mBot.getAnts();

		// unblock hills
		for (Tile myHill : ants.getMyHills()) {
			if (ants.getMyAnts().contains(myHill)
					&& !mBot.orders.containsValue(myHill)) {
				for (Aim direction : Aim.values()) {
					if (doMoveDirection(myHill, direction)) {
						break;
					}
				}
			}
		}
	}

	/**
	 * Gets the heuristic distance. This distance is counted by the no. of cells
	 * apart without square and is different from the distance for
	 * ants.getDistance().
	 * 
	 * @param t1
	 * @param t2
	 * @return
	 */
	public int getHeuristicDistance(Tile t1, Tile t2) {
		int rowDelta = Math.abs(t1.getRow() - t2.getRow());
		int colDelta = Math.abs(t1.getCol() - t2.getCol());
		rowDelta = Math.min(rowDelta, rows - rowDelta);
		colDelta = Math.min(colDelta, cols - colDelta);
		return rowDelta + colDelta;
	}

	protected void clearNodes() {
		for (int i = 0; i < nodes.length; i++) {
			for (int j = 0; j < nodes[i].length; j++) {
				nodes[i][j].clear();
			}
		}
	}

	protected void debugExploreTask() {
		Iterator<Entry<Tile, Task>> itr = this.exploreTask.entrySet()
				.iterator();

		while (itr.hasNext()) {
			Entry<Tile, Task> entry = itr.next();
			Tile antLoc = entry.getKey();
			Task task = entry.getValue();

			MyBot.debug.log(Debug.DEBUG_EXPLORE,
					String.format("%s: %s", antLoc, task.route));
		}
	}
}
